Three-dimensional (3D) models in computer graphics are often represented using triangle meshes. Many meshes are typically not optimized for display or simulation performance. In most applications, these initial meshes can usually be replaced by decimated versions that could be approximations of the initial mesh with fewer triangles, making them more suited for particular applications. In many applications it is desired that the decimated mesh should has a maximum distance deviation from the original mesh. This distance could be important for applications that depend on actual physical distances such as 3D scanning, physical simulations, CAD/CAM/CAE/FEA, or visualization applications where the absolute distance could instead be mapped onto a maximum display pixel error deviation.
Some previous work in mesh decimation includes schemes based on edge collapse of meshes [Hughes Hoppe, “Mesh simplification and construction of progressive meshes”, U.S. Pat. No. 5,929,860], [Quadric metric for simplifying meshes with appearance attributes, [U.S. Pat. No. 6,362,820], [U.S. Pat. No. 6,198,486]. In another edge collapse invention [U.S. Pat. No. 6,771,261] a method is described for calculating an absolute distance metric during an iterative edge collapse. Here only a distance from edge to planes is calculated, and the result is an algorithm that does no guaranty a final mesh that is within defined absolute distance boundary. In summary none of the iterative edge collapse simplification schemes preserve an absolute geometric value, such as distance, between the original 3D mesh and the decimated 3D mesh, since no additional data that is saved during collapse, which can handle calculation of absolute geometric values in a correct manner.
Other mesh simplification methods have constraints in order to preserve a certain absolute distance of the 3D mesh upon decimation. The surface envelopes method uses a surface boundary around the object in a pre-process and uses this during the simplification process. [“Simplification Envelopes” (1996 siggraph), Jonathan Cohen, Amitabh Varshney, Dinesh Manocha, Greg Turk, Hans Weber, Pankaj Agarwal, Frederick Brooks, William Wright]. Yet another method comprises pre-calculating a voxel volume around the original mesh object and using this for calculating absolute distances during mesh simplification. [S. Zelinka and M. Garland. “Permission Grids: Practical, Error-Bounded Simplification.” ACM Transactions on Graphics, 21(2), (2002)]. The disadvantages with these methods are that they only allow a limited class of 2-manifold 3D meshes to be simplified within a distance bound. Furthermore they are memory consuming, and time consuming, since surface boundaries have to be pre-calculated and stored. Other drawbacks of these schemes are they do not give access to knowledge about what part of the original mesh that corresponds to a specific part on the reduced mesh.